package leetcode_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *GroupAnagrams_49  Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
 *describe: 将单词转成hash[26] 序列化 成字符串 在map里分组  AC 26% 
 *最好的办法 是直接将string排序
 *2018年5月6日 上午9:18:50
 */
public class GroupAnagrams_49 {
	List<List<String>> res=new ArrayList<List<String>>();
	public static void main(String[] args) {
		GroupAnagrams_49 test=new GroupAnagrams_49();
		//System.out.println(test.compare(new int[] {1,2,5},new int[] {1,2,5} ));
		//String strs[]=new String[] {"eat", "tea", "tan", "ate", "nat", "bat"};
		//String strs[]=new String[] {"cab","tin","pew","duh","may","ill","buy","bar","max","doc"};
		String strs[]=new String[] {"tho","tin","erg","end","pug","ton","alb","mes","job",
				"ads","soy","toe","tap","sen","ape","led","rig","rig","con","wac"
				,"gog","zen","hay","lie","pay","kid","oaf","arc","hay","vet","sat","gap"
				,"hop","ben","gem","dem","pie","eco","cub","coy","pep","wot","wee"
};
		
		test.groupAnagrams(strs);

	}
	
	/**
	 * describe:对String的数组asc编码 AC 27%
	 * 2018年12月25日 下午4:56:21 
	 */
	public List<List<String>> groupAnagrams(String[] strs) {
		 	List<List<String>> res=new ArrayList<List<String>>();
		 	Map<String,List<String>> map=new HashMap<String,List<String>>();
		 	for(String str:strs) {
		 		String asc=asc(str);
		 		if(!map.containsKey(asc)) {
		 			List<String> now=new ArrayList<String>();
		 			now.add(str);
		 			map.put(asc, now);
		 			res.add(now);
		 		}
		 		else {
		 			List<String> now=map.get(asc);
		 			now.add(str);
		 		}
		 	}
		 	return res;
	}
	
	public String asc(String str) {
		int []hash=new int[26];
		char []chars=str.toCharArray();
		for(char c:chars) {
			hash[c-'a']++;
		}
		StringBuilder sb=new StringBuilder();
		for(int i:hash)
			sb.append(i).append("#");
		return sb.toString();
	}
	
	
	public List<List<String>> groupAnagrams1(String[] strs) {
		int pos=0;//记录当前插入到第几个
		Map<Integer,List<Integer>> maps=new HashMap<Integer,List<Integer>>();
		for(int i=0;i<strs.length;++i) {
			String str=strs[i];
			List<String> resList=new ArrayList<String>();
			int []asc=this.string2Array(str);//转换成asc数组
			int total=asc[0];
			if(maps.containsKey(total)) {//如果有该数组总和  可能有该单词串 也可能没有
				boolean indexflag=false;
				List<Integer> indexList=maps.get(total);
				for(int index:indexList) {//遍历所有可能的index集合
					List<String> strList=res.get(index);
					String s=strList.get(0);//得到第一个字符串
					boolean compareRes=compare(string2Array(s), asc);
					if(compareRes) {//是相同构成的字符串
						System.out.println(str);
						strList.add(str);
						indexflag=true;
						break;
					}

				}
				if(!indexflag) {
					resList.add(str);
					res.add(resList);
					indexList.add(pos);
					++pos;
				}
			}
			else {
				resList.add(str);
				List<Integer> list=new ArrayList<Integer>();
				list.add(pos);
				maps.put(total, list);
				res.add(resList);
				++pos;
			}
			
		}
		return this.res;
    }
	
	public int[] string2Array(String s) {
		int count=0;
		int res[] =new int[s.length()+1];
		for(int i=0;i<s.length();++i) {
			int asc=s.charAt(i)-97;
			count+=asc;
			res[i+1]=asc;
		}
		res[0]=count;
		return res;
	}
	
	/**
	 * describe: 比较两个asc数组 如果不是同样字符构成的 return 0 如果是同样字符构成的 顺序不一样 return 1  是同样字符 return 2
	 * 2018年5月5日 下午9:36:01
	 * @param a1
	 * @param a2
	 * @return
	 * boolean
	 */
	/*public int compare(int [] a1,int []a2) {
		boolean flag=true;
		if(a1.length!=a2.length)
			return 0;
		for(int i=0;i<a1.length;++i) {
			if(a1[i]!=a2[i]) {
				flag=false;
				break;//不是相同字符串
			}
		}
		if(flag)
			return 2;
		Arrays.sort(a1);
		Arrays.sort(a2);
		for(int i=0;i<a1.length;++i)
			if(a1[i]!=a2[i])
				return 0;
		return 1;
	}*/
	
	public boolean compare(int []a1,int [] a2) {
		if(a1.length!=a2.length)
			return false;
		Arrays.sort(a1);
		Arrays.sort(a2);
		for(int i=0;i<a1.length;++i)
			if(a1[i]!=a2[i])
				return false;
		return true;
	}

}
